package com.example.system.class23;

/**
 * @Date 2022/8/24
 * @Author Jonathan
 * @Description 经典题目
 */
public class Code01_KillMonster {
    public static void main(String[] args) {
        System.out.printf("possibility: %f", possibility(5, 10, 4));
    }


    public static double possibility(int M, int N, int K) {
        return process(M, N, K) / Math.pow(M + 1, K);
    }

    /**
     * @param M     每次的伤害值在[0~M]
     * @param hp    怪兽还剩hp点血
     * @param times 攻击times次
     */
    public static long process(int M, int hp, int times) {
        if (times == 0) {
            return hp <= 0 ? 1 : 0;
        }
        // 没有血了 剩下的可能次数直接返回
        if (hp < 0) {
            return (long) Math.pow(M + 1, times);
        }
        long ans = 0;
        for (int i = 0; i <= M; i++) {
            ans += process(M, hp - i, times - 1);
        }
        return ans;
    }

    // 改动态规划  斜率优化
}
